package com.kingwood.algorithm.zuochengyun.dandiaozhan;

/**
 * @Author 22025812
 * @Description: TODO
 * @Date: 2024/3/13 16:29
 * @Modified By：
 * @Version 1.0
 */
public class Code01_MaximumWidthRamp {
    public int maxWidthRamp1(int[] nums) {
        int ans = 0;
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            int cur = nums[i];
            int width = 0;
            for (int j = i + 1; j < len; j++) {
                if (nums[j] >= cur) {
                    width = j - i;
                }
            }

            ans = Math.max(ans, width);
        }

        return ans;
    }

    public static int MAXN = 50001;

    public static int[] stack = new int[MAXN];

    public static int r;

    public int maxWidthRamp2(int[] nums) {
        // 令r=1相当于0位置进栈了
        // stack[0] = 0，然后栈的大小变成1
        r = 1;
        int len = nums.length;
        for (int i = 1; i < len; i++) {
           if (nums[i] < nums[stack[r-1]]) {
               stack[r++] = i;
           }
        }

        int ans = 0;
        for (int j = len - 1; j >= 0; j--) {
            while (r > 0 && nums[j] >= nums[stack[r-1]]) {
                ans = Math.max(ans, j - stack[--r]);
            }
        }

        return ans;
    }
}
